Search Results

Documents authored by Pelecanos, Angelos

Document
DOI: 10.4230/LIPIcs.ITCS.2024.72
Classical vs Quantum Advice and Proofs Under Classically-Accessible Oracle

Authors: Xingjian Li, Qipeng Liu, Angelos Pelecanos, and Takashi Yamakawa

Published in: LIPIcs, Volume 287, 15th Innovations in Theoretical Computer Science Conference (ITCS 2024)

Abstract
It is a long-standing open question to construct a classical oracle relative to which BQP/qpoly ≠ BQP/poly or QMA ≠ QCMA. In this paper, we construct classically-accessible classical oracles relative to which BQP/qpoly ≠ BQP/poly and QMA ≠ QCMA. Here, classically-accessible classical oracles are oracles that can be accessed only classically even for quantum algorithms. Based on a similar technique, we also show an alternative proof for the separation of QMA and QCMA relative to a distributional quantumly-accessible classical oracle, which was recently shown by Natarajan and Nirkhe.
Cite as

Xingjian Li, Qipeng Liu, Angelos Pelecanos, and Takashi Yamakawa. Classical vs Quantum Advice and Proofs Under Classically-Accessible Oracle. In 15th Innovations in Theoretical Computer Science Conference (ITCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 287, pp. 72:1-72:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{li_et_al:LIPIcs.ITCS.2024.72,
  author =	{Li, Xingjian and Liu, Qipeng and Pelecanos, Angelos and Yamakawa, Takashi},
  title =	{{Classical vs Quantum Advice and Proofs Under Classically-Accessible Oracle}},
  booktitle =	{15th Innovations in Theoretical Computer Science Conference (ITCS 2024)},
  pages =	{72:1--72:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-309-6},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{287},
  editor =	{Guruswami, Venkatesan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2024.72},
  URN =		{urn:nbn:de:0030-drops-196009},
  doi =		{10.4230/LIPIcs.ITCS.2024.72},
  annote =	{Keywords: quantum computation, computational complexity}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact